با استفاده از پایتون و نتورک ایکس
محمد حیدری
www.bigdataworld.ir
m_heydari@modares.ac.ir moh.heydari@mail.sbu.ac.ir heydari.mohammad8@gmail.com
نصب کتابخانه نتورک ایکس
#pip install networkx
نسخه نتورک ایکس
print('NetworkX version: {}'.format(nx.__version__))
from IPython.display import Image
import collections
import itertools
import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd
from networkx.algorithms.community import k_clique_communities, girvan_newman
from networkx.algorithms import community
import community
import numpy as np
import pandas as pd
import scipy.spatial as spt
%matplotlib inline
from networkx.algorithms import bipartite
Graph: Undirected graph, allows self-loops
DiGraph: Directed graph, allows self-loops
MultiGraph: Undirected graph with parallel edges, allows self-loops
MultiDiGraph: Directed graph with parallel edges, allows self-loops
G = nx.Graph()
D = nx.DiGraph()
MG = nx.MultiGraph()
MDG = nx.MultiDiGraph()
نمایش یک گراف ابتدایی
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C')])
nx.draw(G, node_size=500, node_color='green', with_labels=True)
ماتریس همسایگی یالهای میان گرههای گراف را نمایش می دهد
درایه ماتریس نشان می دهد آیا بین دو گره الف و ب یالی برقرار است یا خیر
در ماتریس همسایگی اگر گراف طوقه نداشته باشد درایه های قطر اصلی همگی صفر هستند
Adjacency Matrix A $n x n$ matrix:
0 1 1 G = [[0, 1, 1],
1 0 1 [1, 0, 1],
1 1 0 [1, 1, 0]]
Adjacency List A list of neighbors:
A: B, C G = {'A': ['B', 'C'],
B: A, C 'B': ['A', 'C'],
C: A, B 'C': ['A', 'B']}
Edge List A list of edges:
A B G = [['A', 'B'],
A C ['A', 'C'],
B C ['B', 'C']]
NetworkX uses a dictionary of dictionaries based Adjacency List format which is fast and ligthweight for sparse graphs. This approach is inspired on Guido van Rossum's essay Python Patterns - Implementing Graphs and in the work of David Eppstein on Python Algorithms and Data Structures.
This approach allows for natural expressions such as:
Internally the node $n$ is a key in the $G.adj$ dictionary, values are themselves dictionaries with neighbors as keys and another dictionary as value that holds edge attributes.
So NetworkX graphs are "dictionaries all the way down". This is not exactly true in version 2.0 but it is safe for users to think of it this way.
print(G.adj)
چک موجودیت یک نود در گراف
'A' in G
چاپ نودهای گراف با استفاده از حلقه دوست داشتنی
for node in G:
print(node)
نمایش تعداد آیتم ها در گراف
len(G)
# Create an undirected Graph
G = nx.Graph()
# One node at a time
G.add_node(1) # "method" of G
# A list of nodes
G.add_nodes_from([2, 3])
# A container of nodes
H = nx.path_graph(10)
G.add_nodes_from(H) # G now contains the nodes of H
# In contrast, you could use the graph H as a node in G.
G.add_node(H) # G now contains Graph H as a node
nx.draw(G, with_labels=True, node_color='green')
# Adding a single edge
G.add_edge(1, 2)
# Add a list of edges
G.add_edges_from([(1, 2), (1, 3)])
# Add from a container of edges
G.add_edges_from(H.edges())
nx.draw(G, with_labels=True, node_color='green')
from google.colab import files
up = files.upload()
df = pd.read_excel('the_data.xlsx', columns= ['source', 'target'])
df.head()
g = nx.from_pandas_edgelist(df,'source','target')
print(nx.info(g))
print(nx.diameter(g))
print(nx.is_connected(g))
g.nodes
g.edges
deg = dict(g.degree())
maxDeg = max(degrees.values())
maxDegKey = [i for i in degrees.keys() if degrees[i] == maxDeg]
print(maxDeg)
print(maxDegKey)
plt.figure(figsize = (15,15))
pos = nx.kamada_kawai_layout(g)
node_colors = [ g.degree(n) for n in g ]
node_size = [30000*nx.betweenness_centrality(g)[n] for n in g]
nx.draw(g,pos = pos,node_color=node_colors, node_size=node_size,with_label = False,
edge_color='0.6',alpha = 1,width = 0.3, cmap = plt.cm.Blues_r )
plt.axis('off')
#plt.tight_layout()
plt.show()
نحوه اتصال یک نود به نودهای دیگر در یک شبکه اجتماعی میتواند اطلاعاتی راجع به مهم بودن و یا مهم نبودن آن نود در کاربردهای خاص مشخص نماید
مثال میتوانیم مشخص کنیم کدام نود در انتشار شایعه بیشترین تاثیر را در یک شبکه اجتماعی دارد
بینابینی یک نود خاص در شبکه عبارت است از تعداد کوتاهترین مسیرهای میان نودهای شبکه که از یک نود خاص رد میشوند
در حقیقت این معیار محاسبه میکند چه تعداد از نودهای شبکه برای ارتباط سریعتر با هم (با واسطه کمتر) به این نود نیاز دارند
هر چه بینابینی نود زیادتر باشد یعنی اینکه نود در مکان استراتژیک تری قرار گرفته است
نزدیکی عبارت است از عکس متوسط فاصله یک نود تا نودهای دیگر گراف
نودی که دارای بیشترین مقدار نزدیکی است سرعت دسترسی بیشتری به نودهای دیگر دارد و
میتواند در مدت زمان کمی به همه نودها اطلاعات ارسال نماید یا از آنها اطلاعات بگیرد
degCent = nx.degree_centrality(g)
closeCent = nx.closeness_centrality(g)
betCent = nx.betweenness_centrality(g)
pageCent = nx.pagerank(g)
# یک تابع تعریف می کنیم که معیارهای مرکزیت به دست آمده را به صورت مرتب شده به ما بازگرداند
def impNodes(centrality,n = 5):
sortedCent = sorted(centrality.items(), key=lambda x:x[1], reverse=True)[:n]
return sortedCent
print('مرکزیت درجه')
pprint(impNodes(degCent))
print('\n')
print('مرکزیت نزدیکی')
pprint(impNodes(closeCent))
print('\n')
print('مرکزیت بینابینی')
pprint(impNodes(betCent))
print('\n')
print('مرکزیت پیج رنک')
pprint(impNodes(pageCent))
print('\n')
import seaborn as sns
centrality_measures = {
'degree': degCent,
'betweenness': betCent,
'closeness': closeCent,
'page Rank' : pageCent
}
centrality = pd.DataFrame(centrality_measures)
centrality.head()
پیرپلات، نوعی نمودار توزیعی است که اساساً به رسم یک نمودار مشترک برای کلیه ی ترکیبات ممکن ستون های عددی و بولی در دیتاست شما می پردازد
ما فقط باید دیتافریم خود را به عنوان پارامتربه تابع پیرپلات ارسال کنیم
با استفاده از این نمودار می توان گفت که آیا داده ها بطور عادی توزیع می شود یا خیر
sns.pairplot(centrality)
روش جاکارد تعداد همسایه های مشترک دو گره / تعداد کل همسایه هاشون
#یک تابع تعریف می کنیم که محتمل ترین پیوند های پیشبینی شده رو برای ما چاپ می کنه
def topSimLink(pred, n = 5):
pred_dict={}
#s = source, t = target
for s,t, p in pred:
pred_dict[(s,t)] = p
# دیکشنری به دست آمده رو مرتب می کنیم تا ببینیم احتمال تشکیل کدام یک از لینک ها در شبکه بیشتره
pprint( sorted(pred_dict.items(), key = lambda x:x[1], reverse=True)[:n] )
# تابع زیر ضریب ژاکارد برای همه جفت گره هایی در شبکه که با هم متصل نیستند رو محاسبه می کنه
jaccard = nx.jaccard_coefficient(g)
# تبدیل به دیکشنری می کنم
topSimLink(jaccard)
روش اتصال ترجیحی (Preferential Attachment)
prefAtt = nx.preferential_attachment(g)
topSimLink(prefAtt)
# برای نصب این کتابخونه می تونید کد زیر رو اجرا کنید
!pip install python-louvain
هر تکرار از دو فاز تشکیل شده است
فاز اول) بیشینه کردن پیمانگی به طور محلی با جابجایی رئوس در خوشهها
فاز دوم) ساخت خوشههای بدست آمده در فاز قبلی و تولید شبکه جدید
دوفاز به طور متناوب تکرار میشوند تا جایی که دیگر افزایشی در پیمانگی رخ ندهد.
#first compute the best partition
%matplotlib inline
partition = community.best_partition(g)
#drawing
size = float(len(set(partition.values())))
pos = nx.spring_layout(g)
count = 0.
for com in set(partition.values()) :
count = count + 1.
list_nodes = [nodes for nodes in partition.keys()
if partition[nodes] == com]
nx.draw_networkx_nodes(g, pos, list_nodes, node_size = 40,
node_color = str(count / size))
#plt.figure(figsize=(12,12))
#plt.figure(figsize=(20,15))
#plt.figure(3,figsize=(12,12))
nx.draw_networkx_edges(g, pos, alpha=0.5)
plt.savefig("d:Community1.png")
plt.show()
[patterns for patterns in nx.__dir__() if patterns.endswith('_layout')]
plt.figure(figsize=(22, 22))
plt.savefig("Viz1.png")
nx.draw(g,node_color='blue')
plt.title('Graph Representation', size=15)
plt.show()
degree_sequence = sorted([d for n, d in g.degree()], reverse=True) # degree sequence
# print "Degree sequence", degree_sequence
degreeCount = collections.Counter(degree_sequence)
deg, cnt = zip(*degreeCount.items())
fig, ax = plt.subplots()
plt.bar(deg, cnt, width=0.80, color='b')
plt.title("Degree Histogram")
plt.ylabel("Count")
plt.xlabel("Degree")
ax.set_xticks([d + 0.4 for d in deg])
ax.set_xticklabels(deg)
# draw graph in inset
plt.axes([0.4, 0.4, 0.5, 0.5])
#Gcc = sorted(nx.connected_component_subgraphs(g), key=len, reverse=True)[0]
Gcc = sorted(nx.connected_components(g), key=len, reverse=True)[0]
pos = nx.spring_layout(g)
plt.axis('off')
import matplotlib.pyplot as plt
plt.figure(figsize=(20,15))
nx.draw_networkx_nodes(g, pos, node_size= 250, alpha=0.9)
nx.draw_networkx_edges(g, pos, alpha=0.7)
#plt.figure(figsize=(20,10))
plt.savefig("Hist.png")
plt.tight_layout()
plt.show()
pos = nx.circular_layout(g)
betCent = nx.betweenness_centrality(g, normalized=True, endpoints=True)
node_color = [-10 * g.degree(v) for v in g] #node color refers to degree centrality
node_size = [v * 1900 for v in betCent.values()] #node size refers to betweenness centrality
plt.figure(figsize=(14,14))
nx.draw_networkx(g, pos=pos,
node_color=node_color,
node_size=node_size, with_labels = True, font_size = 6)
plt.savefig("graph_Circular.png")
plt.axis('off')
plt.title('Collaboration Network of Notable IR Universities base on Most Communication', size = 10)
plt.show('Graph')
pos = nx.spring_layout(g)
betCent = nx.betweenness_centrality(g, normalized=True, endpoints=True)
node_color = [-10 * g.degree(v) for v in g] #node color refers to degree centrality
node_size = [v * 1900 for v in betCent.values()] #node size refers to betweenness centrality
plt.figure(figsize=(14,14))
nx.draw_networkx(g, pos=pos,
node_color=node_color,
node_size=node_size, with_labels = True, font_size = 6)
plt.savefig("graph_Spring_Bet.png")
plt.axis('off')
plt.title('Collaboration Network of Notable IR Universities base on Most Communication', size = 10)
plt.show('Graph')
poses = [nx.spectral_layout(g),nx.random_layout(g),nx.spring_layout(g), nx.fruchterman_reingold_layout(g)]
titles = ['spectral_layout','random_layout','fruchterman_reingold_layout','spring_layout']
fig = plt.figure(figsize = (20,20))
for i in range(0,4):
fig.add_subplot(2,2,i+1)
node_colors = [ g.degree(n)*10 for n in g ]
nx.draw(g, pos = poses[i], node_color='green')
plt.title(titles[i],fontsize=20)
plt.axis('off')
a = nx.to_numpy_matrix(g, dtype=int)
a = np.asarray(a)
def plotDist(a):
f, ax = plt.subplots(2, 2, figsize=(8,8))
ax[0, 0].imshow(a, cmap = 'Greys', interpolation = 'None')
ax[0, 0].set_title('Adjacency Matrix')
'''D = np.corrcoef(a)
ax[1, 0].imshow(D, cmap = 'Greys', interpolation = 'None')
ax[1, 0].set_title('Correlation coeff.')'''
'''dVec = spt.distance.pdist(a, metric = 'euclidean')
D = spt.distance.squareform(dVec)
ax[0, 1].imshow(D, cmap = 'Greys', interpolation = 'None')
ax[0, 1].set_title('Euclidean Dist.')'''
'''dVec = spt.distance.pdist(a, metric = 'cosine')
D = spt.distance.squareform(dVec)
ax[1, 1].imshow(D, cmap = 'Greys', interpolation = 'None')
ax[1, 1].set_title('Cosine Dist.')'''
plt.savefig("d:Graph Adj Matrix.png")
plotDist(a)
'''import community
def detectCommunities(g):
parts = community.best_partition(g)
values = [parts.get(node) for node in g.nodes()]
plt.axis("off")
nx.draw_networkx(g)
plt.savefig("detectCommunities.png")'''
#برای اضافه کردن این کتابخونه به برنامه منتها باید از دستور زیر استفاده کنید
import community
partition = community.best_partition(g)
#مشخصه اجتماع هر کدوم از گره ها رو به اون گره اضافه می کنیم
nx.set_node_attributes(g,partition,'community')
nx.set_node_attributes(g,node_colors,'colors')
#گراف رو رسم می کنیم
from seaborn import color_palette
palette = sns.color_palette("colorblind", 10)
palette = list(palette)
plt.figure(figsize = (25,15))
pos = nx.kamada_kawai_layout(g)
# براساس اجتماع هر گره یک رنگ به آن تخصیص می دهیم
node_colors = [ palette[i[1]] for i in g.nodes(data = 'community')]
for com in set(partition.values()) :
nx.draw_networkx_nodes(g, pos, node_size = 200,
node_color = node_colors)
nx.draw_networkx_edges(g, pos, alpha=0.5)
plt.savefig('Community Detection_coloral.png')
plt.axis('off')
plt.show()
def who_to_which(n):
for i,j in partition.items():
if partition[i] == n :
print(i)
who_to_which(4)
The pprint module provides a capability to “pretty-print” arbitrary Python data structures in a form which can be used as input to the interpreter.
from pprint import pprint
#یک تابع تعریف می کنیم که محتمل ترین لینک های پیشبینی شده رو برای ما چاپ می کنه
def n_most_likely_links(pred, n = 10):
pred_dict={}
for s,t, p in pred:
pred_dict[(s,t)] = p
# دیکشنری به دست آمده رو مرتب می کنیم تا ببینیم احتمال تشکیل کدام یک از لینک ها در شبکه بیشتره
pprint( sorted(pred_dict.items(), key = lambda x:x[1], reverse=True)[:n] )
# تابع زیر ضریب ژاکارد برای همه جفت گره هایی در شبکه که با هم متصل نیستند رو محاسبه می کنه
pred_jaccard = nx.jaccard_coefficient(g)
# تبدیل به دیکشنری می کنم
n_most_likely_links(pred_jaccard)
pred_r_a = nx.resource_allocation_index(g)
n_most_likely_links(pred_r_a)
pred_pr_at = nx.preferential_attachment(g)
n_most_likely_links(pred_pr_at)
!pip install nxviz
from nxviz import MatrixPlot
from nxviz import ArcPlot
from nxviz import CircosPlot
m = MatrixPlot(g ,node_grouping='community')
plt.figure(figsize = (22,12))
m.draw()
plt.show()
#رنگ و گروه هر کدام از گره در نمودار را بر اساس مشخصه اجتماع آن گره قرار می دهیم
A = ArcPlot(g, nodes_size= 22, node_color='community',node_grouping='community')
plt.figure(figsize = (22,12))
A.draw()
plt.show()
plt.figure(figsize = (12,8))
C= CircosPlot(g ,node_color='community',nodes_grouping='community')
plt.figure(figsize = (22,12))
C.draw()
plt.show()
plt.figure(figsize = (20,15))
pos = nx.fruchterman_reingold_layout(g)
# رنگ گره ها رو بر اساس درجه هر گره تعیین می کنیم. هرچه پر رنگ تر درجه بیشتر
node_colors = [ g.degree(n) for n in g ]
#اندازه گره هایی که رسم می شوند رو بر اساس مرکزیت بینابینی قرار می دیم
node_size = [20000*nx.betweenness_centrality(g)[n] for n in g]
nx.draw_networkx(g,pos = pos,node_color=node_colors, node_size=node_size,
edge_color='1',alpha = 1,width = 0.8, cmap = plt.cm.Blues_r ,label_size = 12, with_labels = False)
plt.savefig('Important_Nodes.jpg', dpi= 1000)
plt.axis('off')
plt.show()
fb_degrees = list(dict(g.degree()).values())
plt.hist(fb_degrees, bins = 30)
#plt.axis('off')
plt.grid(False)
plt.show()
GEXF Designed to be a standard exchange format for graphs (Gephi) nx.read_gexf nx.write_gexf
nx.write_gexf(g, 'gephi.gexf')